package com.example.algorithm.linked_list;

//反转单向链表
//要求：ReverseList方法的参数是原链表头节点，返回结果要求是反转后的链表头节点

// 看了一个小时，大概梳理清楚了它的脉络。算是明白了。曾经看懂过，以后再看，就应该好明白一些了。
// 如果想要看有图示的，可以参考印象笔记算法那个笔记本里面剪藏的这篇文章：看一遍就理解，图解单链表反转 - 掘金
public class ReverseLinkedListSolution02 {

    // 主方法用于测试
    public static void main(String[] args) {
        // 这个head经过下面我们一系列的构造，那么，head节点和许多其他节点一起，构成了一个单向链表。
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        System.out.println("原始链表:");
        printList(head);

        head = reverse(head);

        System.out.println("\n反转后的链表:");
        printList(head);
    }

    // 方法用于反转单向链表
    public static Node reverse(Node head) { // 入参接受原链表的头结点

        // 下面三句不在循环里面，都只会走一遍。相当于纯做第一次的初始化。后续在循环里面，这三个变量的值都会被改变。
        Node prev = null;  // 原始链表，当前节点的前一个节点
        Node current = head; // 原始链表，让头节点成为当前节点。最开始的一个初始值，后面循环每轮会改。
        Node next = null; // 原始链表，当前节点的后一个节点

        // 在循环里面，按照某种合理的顺序改变了prev、current、next
        while (current != null) { // 第一轮:current=1   第二轮：current=2

            next = current.next; // 第一轮：next=2    第二轮：next=3  next算是一个临时变量。
            current.next = prev; // 第一轮：current.next，当前节点的下一个节点被赋值为null   第二轮：current.next = 1

            prev = current; // 第一轮：prev=1    第二轮：prev=2

            current = next; //第一轮：current=2    第二轮：current=3
        }
        head = prev;
        return head;
    }

    // 方法用于打印链表
    public static void printList(Node head) {
        Node temp = head;
        // 循环打印链表。
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

